package main

import (
	"fmt"
	. "local/algorithm/util"
	bst "local/datastructure/tree/binarySearchTree"
)

func diameterOfBinaryTree(root *TreeNode) int {
	diameter := 0
	var dfs func(root *TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return -1
		}

		if root.Left == nil && root.Right == nil {
			return 0
		}

		left := dfs(root.Left) + 1
		right := dfs(root.Right) + 1
		diameter = max(diameter, left+right)
		return max(left, right)
	}
	dfs(root)
	return diameter
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func main() {
	//tree := GenerateTreeLevel([]int{1, 2, 3, 4, 5})
	t := bst.Generate([]int{1, 2, 3, 4, 5})
	diameter := diameterOfBinaryTree(t)
	fmt.Println(diameter)
}
